/**
 * Created with IntelliJ IDEA.
 * Description: 二叉搜索树的模拟实现
 */
class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static TreeNode root = null;

    /**
     * 非递归查找某个元素是否在本树中
     * 时间复杂度：O(N)（最坏情况下二叉搜索树是一棵单叉树）
     * 空间复杂度：O(1)
     * @param val 需要查找的目标值
     * @return
     */
    public TreeNode treeNodeSearch(int val) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val == val) {
                return cur;
            }else if(cur.val > val) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        return null;
    }

    //递归查找，查找的树不一定是本树
    public TreeNode treeNodeSearch(int val,TreeNode root) {
        if(root == null) {
            return null;
        }
        if(root.val == val) {
            return root;
        }else if(root.val > val){
            return treeNodeSearch(val,root.left);
        }else {
            return treeNodeSearch(val,root.right);
        }
    }

    /**
     * 二叉搜索树的插入操作，不考虑树的平衡问题
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param val 需要插入的值
     * @return
     */
    public boolean treeNodeInsert(int val) {
       if(root == null) {
           root = new TreeNode(val);
           return true;
       }
       TreeNode cur = root;
       while(cur != null) {
           if(cur.val > val) {
               if(cur.left == null) {
                   cur.left = new TreeNode(val);
               }else {
                   cur = cur.left;
               }
           }else if(cur.val < val){
               if(cur.right == null) {
                   cur.right = new TreeNode(val);
               }else {
                   cur = cur.right;
               }
           }else {
               return false;
           }
       }
       return true;
    }

    /**
     * 二叉搜索树的删除操作，不考虑树的平衡问题
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param val
     * @return
     */
    public boolean treeNodeDelect(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            if(cur.val == val) {
                return removeNode(parent, cur);
            }else if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        return false;
    }

    private boolean removeNode(TreeNode parent, TreeNode cur) {
        if(cur.left == null && cur.right != null) {
            if(cur == root) {
                root = root.right;
                return true;
            }else {
                if(parent.left == cur) {
                    parent.left = cur.right;
                    return true;
                }else {
                    parent.right = cur.right;
                    return true;
                }
            }
        }else if(cur.left != null && cur.right == null){
            if(cur == root) {
                root = root.left;
                return true;
            }else {
                if(parent.left == cur) {
                    parent.left = cur.left;
                    return true;
                }else {
                    parent.right = cur.left;
                    return true;
                }
            }
        }else if(cur.left != null && cur.right != null) {
            TreeNode target = cur.left;
            TreeNode targetParent = cur;
            while(target.right != null) {
                targetParent = target;
                target = target.right;
            }
            cur.val = target.val;
            if(targetParent == cur) {
                targetParent.left = target.left;
            }else {
                targetParent.right = target.left;
            }
            return true;
        }else {
            if(cur == root) {
                root = null;
            }else if(parent.left == cur) {
                parent.left = null;
            }else {
                parent.right = null;
            }
            return true;
        }
    }

    public void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

public class Test {
    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[] num = {5,3,4,1,7,8,2,6,0,9};
        for(int i = 0; i < num.length; i++) {
            binarySearchTree.treeNodeInsert(num[i]);
        }
        binarySearchTree.treeNodeDelect(6);
        binarySearchTree.inorder(binarySearchTree.root);
    }
}
